//Given a positive integer n, you can apply one of the following operations: 
//
// 
// If n is even, replace n with n / 2. 
// If n is odd, replace n with either n + 1 or n - 1. 
// 
//
// Return the minimum number of operations needed for n to become 1. 
//
// 
// Example 1: 
//
// 
//Input: n = 8
//Output: 3
//Explanation: 8 -> 4 -> 2 -> 1
// 
//
// Example 2: 
//
// 
//Input: n = 7
//Output: 4
//Explanation: 7 -> 8 -> 4 -> 2 -> 1
//or 7 -> 6 -> 3 -> 2 -> 1
// 
//
// Example 3: 
//
// 
//Input: n = 4
//Output: 2
// 
//
// 
// Constraints: 
//
// 
// 1 <= n <= 231 - 1 
// 
// Related Topics 位运算 数学 
// 👍 79 👎 0


package editor.cn;
//Java：Integer Replacement
public class P397IntegerReplacement{
    public static void main(String[] args) {
        Solution solution = new P397IntegerReplacement().new Solution();
        System.out.println(solution.integerReplacement(Integer.MAX_VALUE));
        //1234
        //65535
        //Integer.MAX_VALUE
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int integerReplacement(int n) {
        int count = 0;
        //特殊情况特殊处理，2,147,483,647 int溢出会变负数
        while (n != 1) {
            if (n == Integer.MAX_VALUE) {
                n = --n >> 1;
                count++;
            }
            //num & (~num | 1)该语句是将这个数二进制下最右的第一个一拿出来，所以拿出来的数>1为偶数，==1为奇数
            if ((n & (~n + 1)) == 1) {
                int temp = n >> 1;
                //根据算法要求,还要判断下一个位是否1,下一位不能是最高位,如果temp==1说明此时为最高位
                //1‭111111111111101‬->
                //这种情况下如果+1,下一个还是1,那就要再+1,再>>1
                //如果-1,下一个就是0,直接>>1
                if (temp!=1&&(temp & (~temp + 1)) == 1) {
                    n++;
                } else {
                    n--;
                }
                n = n >> 1;
                count += 2;
            } else {
                n = n >> 1;
                count++;
            }
        }
        return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}